package com.str.graphs;
public class Prim {
  private static int minVertex(Graph g, int[] d, boolean[] visited) { // Find min cost vertex
    int v = 0;
    for (int i=0; i<g.n(); i++)    // Set v to an unvisited vertex
      if (!visited[i]) { v = i; break; }
    for (int i=v+1; i<g.n(); i++)    // Now find smallest D value
      if ((!visited[i]) && (d[i] < d[v])) v = i;
    return v;
  }

  private static void addEdgetoMST(int v1, int v2) {
    System.out.println("Add edge " + v1 + " to " + v2);
  }

  public static void prim(Graph g, int s) {        // Prim's MST algorithm
    boolean[] visited = new boolean[g.n()];
    int[] d = new int[g.n()];         // Distance vertex
    int[] p = new int[g.n()];         // Who's closest
    for (int i=0; i<g.n(); i++) {        // Initialize
      visited[i] = false;
      d[i] = Integer.MAX_VALUE;
    }
    d[s] = 0;
    for (int i=0; i<g.n(); i++) {        // Process the vertices
      int v = minVertex(g, d, visited);
      visited[v] = true;
      if (v != s) addEdgetoMST(p[v], v); // Add edge to MST
      if (d[v] == Integer.MAX_VALUE) return; // Remaining vertices unreachable
      for (int w = g.first(v); w < g.n(); w = g.next(v,w))
        if (d[w] > g.weight(v,w)) {
	      d[w] = g.weight(v,w);         // Update distance
	      p[w] = v;                 // Update who it came from
        }
    }
  }
}
